//堆

function left(i){
    return i*2 + 1;
}
function right(i){
    return i*2 + 2;
}
function swap(arr,i,j){
    [arr[i],arr[j]] = [arr[j],arr[i]];
}

class Heap {
    constructor(arr){
        this.data = [...arr];
        this.size = this.data.length;
    }
    //交换父子节点位置，符合最大堆特征
    heapify(i){
        let max = i;
        if(i >= this.size){
            return;
        }
        const l = left(i);
        const r = right(i);
        if( l<this.size && this.data[l]>this.data[max]){
            max = l;
        }
        if( r<this.size && this.data[r]>this.data[max]){
            max = r;
        }
        if(max === i){
            return;
        }
        swap(this.data,i,max);
        return this.heapify(max);//递归向下执行
    }
    //重构堆，形成最大堆
    rebuildHeap(){
        const L = Math.floor(this.size/2);
        for(let i = L-1;i>=0;i--){
            this.heapify(i);
        }
    }
    //堆排序，形成升序的数组
    sort(){
        for(let i=this.size -1;i>0;i--){
            swap(this.data,0,i);
            this.size--;
            this.heapify(0);
        }
    }
    //是否满足堆性质
    isHeap(){
        const L = Math.floor(this.size/2);
        for(let i=L-1;i>0;i--){
            const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
            const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
            let max = Math.max(this.data[i],l,r);
            if(max !== this.data[i]){
                return false;
            } 
            return true;
        }
    }
    delete(index){
       if(index >=this.size){
           return;
       }
       this.data.splice(index,1);
       this.size--;
       if(this.isHeap()){
           return;
       }
       this.rebuildHeap();
    }
    insert(key){
        this.data[this.size++] = key;
        if(this.isHeap()){
            return;
        }
        this.rebuildHeap();
    }
}
const fun = new Heap([15, 12, 8, 2, 5, 2, 3, 4, 7]);
fun.rebuildHeap();
fun.sort();
console.log(fun.data);

//top K系列
/**
 * 剑指offer 40:最小的k个数
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 */

var getLeastNumbers = function(arr, k) {
    let heap = arr.slice(0,k)
    const buildHeap = (A)=>{
        const L = Math.floor(A.length/2);
        for(let i=L-1;i>=0;i--){
            heapify(A,i);
        }
    }
    const heapify = (A,i)=>{
        let max = i;
        if(i>=A.length) return;
        const l = 2*i + 1;
        const r = 2*i + 2;
        if(l<A.length && A[l]>A[max]){
            max = l;
        }
        if(r<A.length && A[r]>A[max]){
            max = r;
        }
        if(max === i) return;
        swap(A,i,max);
        return heapify(A,max);
    }
    const swap = (A,i,j)=>{
        [A[i],A[j]] = [A[j],A[i]];
    }
    buildHeap(heap);
    for(let i=k;i<arr.length;i++){
        if(heap[0]>arr[i]){
            //替换并堆化
            heap[0] = arr[i];
            heapify(heap,0);
        }
    }
    return heap;
};

/**
 * 347.前k个高频元素
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 */
var topKFrequent = function(nums, k) {
  
};